package com.dataStructure.graph;


import java.beans.Visibility;
import java.util.*;
/**
 * 图的深度优先遍历和二叉树遍历的类比
 *
 */


public class LeetCode {



    public static void main(String[] args) {
        allAc();
    }
    public boolean[] visited;
    public  Integer max = 0;
    public Integer cur  = 0;

    public Integer Enclaves = 0;
    public Integer SumEnclave = 0;

    static List<LinkedList<Integer>> res = new LinkedList<>();
    static LinkedList<Integer> trace = new LinkedList<>();
    public static void  allAc() {
        Scanner in = new Scanner(System.in);
        HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();

        int N = in.nextInt();
        int M = in.nextInt();

        for (int i = 1; i <= N ;i ++) {
            graph.put(i, new LinkedList<>() );
        }

        for (int i = 0; i < M; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            graph.get(s).add(t);

        }
        System.out.println(graph);
        trace.add(1);
        dfs(graph, 1, N);
        for (LinkedList<Integer> list : res) {

            for (int i = 0; i < list.size() - 1; i++) {
                System.out.print(list.get(i) + " ");
            }
            System.out.println(list.get(list.size() - 1));
        }


    }
    public static void dfs (HashMap<Integer, LinkedList<Integer>> graph, Integer curNode, int N) {
        if (curNode == N) {
            res.add(new LinkedList<>(trace));
            return ;
        }
        LinkedList<Integer> toList = graph.get(curNode);

        for (Integer toCity : toList) {
            trace.add(toCity);
            dfs(graph, toCity, N);
            trace.removeLast();
        }

    }

    /**
     * 狄克斯特拉：加权有向图的最短路径长度，和具体路径
     *
     * 到达未处理节点最便宜的节点，更新该节点邻居的节点开销，以及父节点，标记已处理。重复处理
     */
    public void djstl() {
        Scanner in = new Scanner(System.in);
        HashMap<Integer, Integer> parents = new HashMap<>();
        HashMap<Integer, Integer> costs = new HashMap<>();
        HashMap<Integer, Map<Integer, Integer>> graph = new HashMap<>();

        HashSet<Integer> visited = new HashSet<>();

        int N = in.nextInt();
        for (int i = 1; i <= N; i++) {
            graph.put(i, new HashMap<>());
            //初始都是无穷大
            costs.put(i, Integer.MAX_VALUE);
        }

        int M = in.nextInt();


        for (int i = 0; i < M ;i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int v = in.nextInt();
            graph.get(s).put(e, v);
        }

        costs.put(1, 0);

        while (true) {
            int lowCity = findLowerNode(visited, costs);
            if (lowCity == 0) {
                break;
            }
            Map<Integer, Integer> neighbors = graph.get(lowCity);
            for (Integer neighbor : neighbors.keySet()) {
                //邻居开销，找到最小的了
                if (costs.get(neighbor) > neighbors.get(neighbor) + costs.get(lowCity)) {
                    costs.put(neighbor, costs.get(lowCity) + neighbors.get(neighbor));
                    parents.put(neighbor, lowCity);
                }
            }
        }

        System.out.println((costs.get(N)) == Integer.MAX_VALUE ? -1:costs.get(N));


    }
    //返回最便宜的节点
    public Integer findLowerNode(HashSet<Integer> visited, Map<Integer, Integer> costs)  {

        int lowest = Integer.MAX_VALUE;
        int lowCity =0;
        for (Integer city : costs.keySet()) {
            if (costs.get(city) < lowest && !visited.contains(city)) {
                lowCity = city;
                lowest = costs.get(city);
            }
        }
        visited.add(lowCity);
        return lowCity;
    }

    /**
     * https://kamacoder.com/problempage.php?pid=1177
     * 有向图的完全可达性，类通讯录问题
     */
    public void bfs() {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int k = in.nextInt();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        HashSet<Integer> tList = new HashSet<>();
        for (int i = 1; i <= N; i++) {
            tList.add(i);
            graph.put(i, new LinkedList<>());
        }
        for (int i = 0; i < k; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            graph.get(s).add(t);
        }
        HashSet<Integer> visited = new HashSet<>();
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(1);
        while (queue.size() != 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer curArea = queue.poll();
                if (!visited.contains(curArea)) {
                    List<Integer> toAreas = graph.get(curArea);
                    queue.addAll(toAreas);
                }
                visited.add(curArea);
                tList.remove(curArea);
            }
        }
        if (tList.isEmpty()) {
            System.out.println(1);
        } else {
            System.out.println(-1);
        }
    }
    /**
     * 腐烂的橘子
     */
    public int orangesRotting(int[][] grid) {
        LinkedList<int[]> queue = new LinkedList<>();
        int Count = 0;
        for (int i = 0; i < grid.length; i++ ) {
            for (int j = 0; j < grid[0].length ; j++) {
                if (grid[i][j] == 1) {
                    Count++;
                }
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        int line = 0;

        while (queue.size() != 0) {


            int n = queue.size();
            line ++;
            for (int i = 0; i < n; i++) {
                int[] cur = queue.pop();
                int I = cur[0];
                int J = cur[1];

                if (J + 1 < grid[0].length && grid[I][J + 1] ==1   ) {
                    Count--;
                    grid[I ][J + 1] = 2;
                    queue.add(new int[]{I, J + 1});

                }
                if (I + 1 < grid.length  && grid[I + 1][J] == 1  ) {
                    Count--;
                    grid[I + 1][J] = 2;
                    queue.add(new int[]{I + 1, J});
                }

                if (J - 1 > 0 && grid[I][J - 1] ==1 ) {
                    Count--;
                    grid[I][J -1] = 2;
                    queue.add(new int[]{I, J -1});
                }

                if (I - 1 > 0 && grid[I - 1][J] ==1 ) {
                    Count--;
                    grid[I - 1][J] = 2;
                    queue.add(new int[]{I - 1, J});
                }
            }
        }
        System.out.println(Count);
        if (Count > 0) {
            return -1;
        } else
            return line;

    }


    /**
     * 1971. 寻找图中是否存在路径
     */
    public  boolean validPath(int n, int[][] edges, int source, int destination) {
        visited = new boolean[n];
        if (source == destination) {
            return true;
        }
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i,new ArrayList<>());
        }
        for (int[] edge : edges) {
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }

        return dfsPath(map,source,destination,visited);


    }

    private boolean dfsPath(HashMap<Integer, List<Integer>> map, int source, int destination, boolean[] visited) {
        if (source == destination) {
            return true;
        }
        visited[source] = true;

        List<Integer> list = map.get(source);
        for (Integer e : list) {
            if (visited[e]) {
                continue;
            }
            if (dfsPath(map,e,destination,visited)) {
                return true;
            }

        }
        return false;
    }

    /**
     * 130，被围绕的区域
     * @param board
     */
    public void solve(char[][] board) {
        for (int i = 0; i < board[0].length; i++) {
            //遍历第一排
            if (board[0][i] == 'O') {
                dfsSolve(board,0, i);
            }
        }
        for (int i = 0; i < board[0].length; i++) {
            if (board[board.length - 1][i] == 'O') {
                dfsSolve(board, board.length - 1,i);
            }
        }

        //遍历左边第一列
        for (int i = 0; i < board.length; i++ ) {
            if (board[i][0] == 'O') {
                dfsSolve(board,i, 0);
            }
        }

        for (int i = 0 ; i< board.length; i++) {
            if (board[i][board[0].length - 1]   == 'O') {
                dfsSolve(board,i, board[0].length - 1);
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '2') {
                    board[i][j] = 'O';
                }
            }

        }
    }

    private void dfsSolve(char[][] board, int i, int j) {
        if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) {
            return;
        }
        if (board[i][j] != 'O') {
            return;
        }
        board[i][j] = '2';
        dfsSolve(board,i , j + 1);
        dfsSolve(board,i + 1 , j );
        dfsSolve(board,i , j - 1);
        dfsSolve(board,i - 1, j);
    }


    /**
     * 1020,
     * 飞地的数量
     *   @return  的
     */
    public int numEnclaves(int[][] grid) {
        //遍历第一排
        for (int i = 0; i < grid[0].length ; i++) {
            if (grid[0][i] == 1) {
                dfsEnclaves(grid,0, i);
                Enclaves++;
            }
        }
        //遍历最后一排
        for (int i = 0; i < grid[0].length ; i++) {
            if (grid[grid.length - 1][i] == 1) {
                dfsEnclaves(grid,grid.length - 1, i);
                Enclaves++;
            }
        }
        //遍历左边第一列
        for (int i = 0; i < grid.length ; i++) {
            if (grid[i][0] == 1) {
                dfsEnclaves(grid,i, 0);
                Enclaves++;
            }
        }
        //遍历右边第一列
        for (int i = 0; i < grid.length ; i++) {
            if (grid[i][grid[0].length - 1] == 1) {
                dfsEnclaves(grid,i, grid[0].length - 1);
                Enclaves++;
            }
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j< grid[0].length; j++) {
                if (grid[i][j] ==1) {
                    SumEnclave ++;
                }
            }
        }




        return SumEnclave;
    }

    private void dfsEnclaves(int[][] grid, int i, int j) {
        if (i < 0 || i > grid.length -1 ||  j < 0 || j > grid[0].length -1) {
            return;
        }
        if (grid[i][j] != 1) {
            return;
        }
        grid[i][j] = 2;
        dfsEnclaves(grid,i,j + 1);
        dfsEnclaves(grid,i + 1,j );
        dfsEnclaves(grid,i,j -1 );
        dfsEnclaves(grid,i -1,j );

    }


    /**
     * 695，
     * 岛屿的最大面积
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    dfsMaxSland(grid, i , j);
                    max = Integer.max(max,cur);
                    cur = 0;
                }
            }
        }
        return max;
    }

    private void dfsMaxSland(int[][] grid, int i, int j) {
        if (i <0 || i > grid.length -1 || j < 0 || j > grid[0].length - 1) {
            return;
        }
        if (grid[i][j] != 1) {
            return;
        }
        cur += 1;
        grid[i][j] = 2;
        dfsMaxSland(grid,i , j + 1);
        dfsMaxSland(grid,i + 1, j);
        dfsMaxSland(grid,i , j - 1);
        dfsMaxSland(grid,i - 1, j);
    }

    /**
     * 岛屿数量
     * @param grid
     *      * @return
     */
    public int numIslands(char[][] grid) {
        int ct = 0;
        for (int i = 0 ; i < grid.length ; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfsLand(grid,i,j);
                    ct++;
                }
            }
        }
        return ct;
    }

    private void dfsLand(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            return;
        }
        if (grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '2';
        dfsLand(grid,i, j + 1);
        dfsLand(grid,i + 1, j);
        dfsLand(grid,i, j - 1);
        dfsLand(grid,i - 1, j);

    }

    /**
     * 路径问题
     * @param graph
     * @return
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        path.add(0);
        dfs(0,graph);
        return result;

    }

    public void dfs(int x, int[][] graph) {
        if (x == graph.length - 1) {
            path.add(x);
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < graph[i].length ; i++) {
            path.add(graph[x][i]);
            dfs(graph[x][i], graph);

            path.removeLast();
        }
    }
    public  List<List<Integer>> result = new ArrayList<>();

    public LinkedList<Integer> path = new LinkedList<Integer>();
    /**
     * 所有可能的路径
     */
    public List<List<Integer>> allPathsSourceTarget2(int[][] graph) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        visited = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {

            map.put(i,new ArrayList<>());
        }
        for (int i = 0; i < graph.length; i++) {
            int[] ints = graph[i];
            for (int anInt : ints) {
                map.get(i).add(anInt);
            }
        }

        dfsAllPath(visited, map, 0);

        return result;

    }

    private void dfsAllPath(boolean[] visited, HashMap<Integer, List<Integer>> map, int DinDian) {
        if (DinDian == visited.length - 1) {
            result.add(new ArrayList<>(path));
            System.out.println(Arrays.toString(result.toArray()));
            return;
        }
//        visited[DinDian]= true;
        List<Integer> integers = map.get(DinDian);
        for (Integer e : integers) {
//            if (visited[e]) {
//                continue;
//            }
            path.add(e);
            dfsAllPath(visited, map, e);
            path.removeLast();
        }


    }
}
